package LeetCodeHot100TopInterview;

import java.util.LinkedList;
import java.util.List;

public class Q046_QuanPaiLie {
    //全排列问题
    //深度优先广度优先都可以  ==> 深度优先 ==> 基于交换
    //本题类似 Q039 组合问题 需要考虑剪枝去重?
    static List<List<Integer>> ans = null;
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0){
            return new LinkedList<>();
        }
        ans = new LinkedList<>();
        process(nums, 0);
        System.out.println(ans);
        return null;
    }
    public void process(int[] nums, int index) {
        //base case
        if (index == nums.length){
            LinkedList<Integer> tmp = new LinkedList<>();
            for (int num : nums) {
                tmp.add(num);
            }
            ans.add(tmp);
            return;
        }
        //我跟我自己交换不行吗
        for (int i = index; i < nums.length; i++) {
            swap(nums, i, index);
            process(nums, index + 1);
            //恢复现场
            swap(nums, i, index);
        }
    }

    public void swap(int[] nums, int x, int y){
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }

    public static void main(String[] args) {
        Q046_QuanPaiLie fun = new Q046_QuanPaiLie();
        fun.permute(new int[]{1,2,3});
    }
}
